import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/19 16:39
 * @description DFS O(n^2)
 */
public class Solution {
    public static void main(String[] args) {

    }
    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return 0;
        }
        // 以当前节点为根节点，到子节点的和为targetSum次数
        int ret = rootSum(root, targetSum);
        // 左子树的次数
        ret += pathSum(root.left, targetSum);
        // 右子树的次数
        ret += pathSum(root.right, targetSum);
        return ret;
    }

    public int rootSum(TreeNode root, int targetSum) {
        int ret = 0;

        if (root == null) {
            return 0;
        }
        int val = root.val;
        if (val == targetSum) {
            ret++;
        }

        ret += rootSum(root.left, targetSum - val);
        ret += rootSum(root.right, targetSum - val);
        return ret;
    }

}
